// 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
// 题目数据保证答案符合 32 位整数范围。

// 输入：nums = [1,2,3], target = 4
// 输出：7
// 解释：
// 所有可能的组合为：
// (1, 1, 1, 1)
// (1, 1, 2)
// (1, 2, 1)
// (1, 3)
// (2, 1, 1)
// (2, 2)
// (3, 1)
// 请注意，顺序不同的序列被视作不同的组合。

// 不是单纯的组合问题, 数字可重复选择 且不同序列视作不同组合！！！
// 无法用组合总和3的解法做, 因为路径太多太复杂; 
// 1，2组合总和为5还好，到1，2组合总和为100时，单纯的回溯就搜索不动了！！！ 超出时间限制
// 不用得到具体的组合表示

// 使用动态规划，「从底向上」递推；

int combinationSum4(int* nums, int numsSize, int target){
    // dp[i]表示和为i的组合的个数， 注意给定数组中都是正整数且无重复元素
    // 转移方程: dp[i] = dp[i - nums[0]] + dp[i - nums[1]] + ………… + dp[i - nums[n]]
    // 初始状态: dp[0] = 1; 表示nums[i]的值为i，即恰好有一个数的值为target
    int *dp = calloc(target+1, sizeof(int));
    dp[0] = 1;

    // 例子：{1,2,3} target:7
    // dp[7] = dp[6] + dp[5] + dp[4]
    for (int i = 1; i <= target; i++) { //求和为i的组合
        for (int j = 0; j < numsSize; j++) {
            if (i - nums[j] >= 0) { 
                // 有溢出情况 
                dp[i] =(dp[i] > INT_MAX - dp[i - nums[j]] ? INT_MAX : dp[i] + dp[i-nums[j]]); 
                //dp[i] += dp[i - nums[j]];
            }
        }
    }
    int res = dp[target];
    free(dp);
    return res;
}
